As is known in the art, there are situations in which it is desirable to plan a path for a vehicle. One known path planning technique is known as Rapidly-Exploring Random Trees (RRTs). However, RRT methods deal with small numbers of stationary obstacles and assume that there are fixed regions of the environment that must be avoided. One disadvantage of such methods is that they do not address moving objects, uncertain environments, or uncertain vehicle movements.
U.S. Pat. No. 6,259,988, discloses a real-time mission adaptable route planner that presents a path planning method for finding a path in two or three dimensions where vertices consist of nodes in a predetermined grid. The method disclosed in the '988 patent is essentially a graph search method that adds nodes to the existing path in a greedy manner. Nodes in the grid have ‘cost’ values associated with them and these costs are used in determining how to extend the path. Candidate nodes are added to the path using criteria based on the cost function at the node. To add nodes to the path a cost function is used. The constraints that are considered are maximum turn angle, minimum segment length, and maximum path length.
In U.S. Pat. No. 6,259,988, a further route planning method is disclosed in which costs are assigned to every cell in a predetermined grid so as to necessitate the computation of costs for the entire area. The costs for the entire grid are updated every iteration.